package linkedlist;

import org.junit.Test;

import static linkedlist.ListNode.buildList;
import static linkedlist.ListNode.printList;

public class ReverseNodesInKGroup25 {

    @Test
    public void test() {
        reverseKGroup(buildList(1,2,3,4,5), 5);
        reverseKGroup(buildList(1,2,3,4,5), 4);
        reverseKGroup(buildList(1,2,3,4,5), 3);
        reverseKGroup(buildList(1,2,3,4,5), 2);
        reverseKGroup(buildList(1,2,3,4,5), 1);
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        printList(head, "origin");
        if (head == null || head.next == null || k <= 1) {
            printList(head, "reversed");
            return head;
        }
        ListNode prevHead = new ListNode();
        prevHead.next = head;

        ListNode prevStart = prevHead;
        while (prevStart != null && prevStart.next != null) {
            prevStart = reverseKNodesAndReturnNewLast(prevStart, prevStart.next, k);
        }
        printList(prevHead.next, "reversed");
        return prevHead.next;
    }

    public ListNode reverseKNodesAndReturnNewLast(ListNode prevStart, ListNode start, final int k) {
        if (!checkNodeCount(start, k)) {
            return null;
        }
        int i = 0;
        ListNode prev = null;
        ListNode curr = start;
        // 四部曲
        while (i < k) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
            i++;
        }
        // start已经变成了last
        start.next = curr;

        // prev变成了first
        prevStart.next = prev;

        return start;
    }

    public boolean checkNodeCount(ListNode start, final int k) {
        int i = 1;
        while (i < k && start.next != null) {
            start = start.next;
            i++;
        }
        return i == k;
    }
}
